
"""
1161. 最大层内元素和
"""
import collections
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        """
        利用层序遍历
        """
        max_sum = 0
        level = 0
        index = 0

        if not root:
            return level

        # 辅助队列(永远只存储一层节点)
        q = collections.deque()
        q.append(root)

        # 两个遍历，第一个遍历层数，第二个遍历每层的各个元素
        while q:
            index += 1
            count = 0
            # 控制节点数，保证每次while循环只取出一层
            size = len(q)

            for i in range(0, size):
                # 取出队列第一个元素
                cur = q.popleft()
                count += cur.val
                # 将当前节点的左右子节点存储到队列中，用于遍历下一层
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)

            if max_sum < count:
                max_sum = count
                level = index

        return level